НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №2
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «РЕКУРСИВНІ АЛГОРИТМИ»
Варіант № 16
Дата «15» квітня 2022
Київ 2022
Мета роботи: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціями.
Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.
Завдання:
/
рис 1.
Теоретичні відомості:
Мова С підтримує можливість звернення функції самої до себе — рекурсію.Розрізняють пряму і непряму рекурсії. Функція називається прямо рекурсивною, якщо містить у своє му тілі виклик самої себе. Якщо ж функція викликає іншу функцію, що у свою чергу викликає першу, то така функція називається непрямо рекурсивною.
Рекурсивні функції найчастіше використовуються для компактної реалізації рекурсивних алгоритмів.
Класичні приклади використання рекурсії — реалізація операції піднесення до степеня і обчислення факторіала числа. Зазначимо, що ці приклади популярні тільки через їхню зруч ність для пояснення поняття рекурсії, однак вони не дають ви грашу в програмній реалізації порівняно з ітераційним спосо бом розв’язання цих задач.
Розглянемо рекурсивну функцію обчислення факторіала. Для того щоб одержати значення факторіала числа n!, необхід но помножити на n факторіал числа (n-1)!.Ураховуючи, що 0! = 1 та 1! = 1, наведемо приклад цієї функції:
double factorial(double n){//Метод обчислювання факторіалу
if(n <= 1.0)
return 1.0;
else
return (n*factorial(n-1));
}
Хід роботи:
Написано програмний код, який виконує завдання різними способави на вібір, або за допомогою рекурсивної функції, або без неї. Для цього було створено два метода. Результат розрахунків було перевірено калькулятором, помилок не знайдено.
Було проведено оцінку часової складності алгоритму та порівняно час роботи та кількість ітерацій з різною для різної кількості елемнтів добутку(10, 50, 100, 500). Оцінку часу роботи наведено нижче у вигляді таблиці та графіку.
Було створенно два методів для полегшення метода main, кожен метод для одного варіанту виповнення завдання.
У MultRec ми маємо рекурсивну функцію тому вона виконується лише n разів. Також ми маємо if і тіло у середині спочатку робиться n-1 разів, а потім ще один раз, тому усього буде n разів. Загалом метод спростити до n+n=2n = Θ(n).
Розмір
Складність
Кілкість ітерацій
Час виконання
10
Θ (N)
20
0.035 msec
50
100
0.043 msec
100
200
0.063 msec
500
1000
0.165 msec
Для другого завдання використано метод Mult, де ми маємо лише один цикл тому його можна звести до 4+2n+n=4+3n = Θ(n).
Розмір
Складність
Кілкість ітерацій
Час виконання
10
Θ (N)
34
0.053 msec
50
154
0.076 msec
100
303
0.095 msec
500
1504
0.134 msec
/
Код програми:
Посилання на код:
https://replit.com/join/bdvvosqxdc-tr-15khavkin
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
double MultRec(double mult, int t, int n){
if(t<n){
return(pow(sin(t),3)/(pow(t,2)-1))*MultRec(mult,t+1,n);
} else if (t==n){
return pow(sin(t),3)/(pow(t,2)-1);
}else return 1;
}
double Mult(double mult, int t, int n){
for(int i=t;i<n;i++){
mult=mult*(pow(sin(i),3)/(pow(i,2)-1));
}
return mult;
}
int main(void) {
int n,x,s;
printf("\nЗавдання:\n n\n ┌──┐ sin³t\nf=│ │ ───── , n є [t;n]\n │ │ t²-1\n t=2\n\nВедіть n: ");
scanf("%d", &n);
printf("\nВикористання алгоритму з рекурсивною функцією(1) або без(2): ");
scanf("%d", &x);
double f;
clock_t ttime1,ttime2,ttime3,ttime4;
switch(x){
case 1:
ttime1 = clock();
f=MultRec(1,2,n);
ttime2 = clock();
printf("\nTime of 1 task: %lf msec", (double)(ttime2-ttime1)/CLOCKS_PER_SEC*1000);
printf("\n\nf=%.30...
